//Zhuk Artsem, 399

#pragma once

#include <vector>
#include <string>
#include <assert.h>
#include <fstream>
#include <algorithm>
#include <map>
#include <iterator>

typedef std::vector<int>::const_iterator iterator;
typedef std::vector<int>::const_reverse_iterator reverse_iterator;

//std::make_reverse_iterator belongs to c++14!
reverse_iterator make_reverse_iterator(const iterator it){
	return reverse_iterator(it);
}

//maintains array with indices in [-n,n]
class VectorWithNegativeIndices{
private:
	std::vector<int> array_;
	int shift_;
public:
	explicit VectorWithNegativeIndices(int n) :array_(2 * n + 1), shift_(n){};
	int &operator[](int positions){
		return array_[shift_ + positions];
	}
};

template<class Iterator>
int getLongestCommonPrefixLength(Iterator begin1, Iterator end1, Iterator begin2, Iterator end2){
	int recipe = 0;

	while (begin1 != end1 && begin2 != end2 && *begin1 == *begin2){
		++begin1;
		++begin2;
		++recipe;
	}

	return recipe;
}

namespace DistanceFounder{

	int getDiagonalLength(int width, int height, int diagonal){ // Enumerate all diagoanals as (-height, wedth]. Returns diagonal's length with number number.
		int y_coordinate, x_coodinate;
		if (diagonal >= 0)
			x_coodinate = diagonal, y_coordinate = 0;
		else
			x_coodinate = 0, y_coordinate = -diagonal;
		return std::min(width - x_coodinate, height - y_coordinate);
	}

	void setPositionOnDiagonal(int diagonal, int position, int size1, int size2, int &position1, int &position2){//gets position on diagonal of rectangle
		if (diagonal>= 0)
			position1 = diagonal, position2 = 0;
		else
			position1 = 0, position2 = -diagonal;

		position1 += position;
		position2 += position;

		int gap = std::max(position1 - size1, position2 - size2);

		if (gap > 0){
			position1 -= gap;
			position2 -= gap;
			position -= gap;
		}

		assert(position1 <= size1);
		assert(position2 <= size2);
	}

	template<class Iterator>
	int getDistance(Iterator begin1, Iterator end1, Iterator begin2, Iterator end2){
		int size1 = std::distance(begin1, end1);
		int size2 = std::distance(begin2, end2);

		VectorWithNegativeIndices position(size1 + size2);
		int distance = -1;

		while (position[size1 - size2] != std::min(size1, size2)){
			++distance;
			for (int diagonal = -distance; diagonal <= distance; diagonal += 2)
			if (-size2 <= diagonal && diagonal <= size1){

				int max_step = 0;

				if (diagonal - 1 >= std::max(-size2, -distance))
					max_step = std::max(max_step, position[diagonal - 1] + (diagonal - 1 < 0 ? 1 : 0));

				if (diagonal + 1 <= std::min(size1, distance))
					max_step = std::max(max_step, position[diagonal + 1] + (diagonal + 1 > 0 ? 1 : 0));

				int position1, position2;
				setPositionOnDiagonal(diagonal, max_step, size1, size2, position1, position2);

				position[diagonal] = max_step + getLongestCommonPrefixLength(begin1 + position1, end1, begin2 + position2, end2);
			}
		}

		return distance;
	}

	int getDistance(const std::vector<int> &sequence1, const std::vector<int> &sequence2){
		return getDistance(sequence1.begin(),sequence1.end(),sequence2.begin(),sequence2.end());
	}

	template<class Iterator>
	VectorWithNegativeIndices getDistArray(Iterator begin1, Iterator end1, Iterator begin2, Iterator end2, int dist_bound){

		int size1 = std::distance(begin1, end1);
		int size2 = std::distance(begin2, end2);

		VectorWithNegativeIndices distance_array(size1 + size2);

		for (int dist = 0; dist <= dist_bound; ++dist)
		for (int currentDiagonal = -dist; currentDiagonal <= dist; currentDiagonal += 2)
		if (-size2 <= currentDiagonal && currentDiagonal <= size1){

			int max_step = 0;

			if (currentDiagonal - 1 >= std::max(-size2, -dist))
				max_step = std::max(max_step, distance_array[currentDiagonal - 1] + (currentDiagonal - 1 < 0 ? 1 : 0));

			if (currentDiagonal + 1 <= std::min(size1, dist))
				max_step = std::max(max_step, distance_array[currentDiagonal + 1] + (currentDiagonal + 1 > 0 ? 1 : 0));


			int position1, position2;

			setPositionOnDiagonal(currentDiagonal, max_step, size1, size2, position1, position2);
			
			distance_array[currentDiagonal] = max_step + getLongestCommonPrefixLength(begin1 + position1, end1, begin2 + position2, end2);
		}

		return distance_array;
	}

	void pushToRecipe(std::vector<int> &recipe, int modification = 0){
		recipe.push_back(modification);
	}


	void setDivisionPoint(iterator begin1, iterator end1, iterator begin2, iterator end2, int distance, int &position1, int &position2){
		int size1 = std::distance(begin1, end1), size2 = std::distance(begin2, end2);
		int left_bound = (distance + 1) / 2;
		int right_bound = distance - left_bound;
		VectorWithNegativeIndices left = getDistArray(begin1, end1, begin2, end2, left_bound);


		VectorWithNegativeIndices pre_right = getDistArray(make_reverse_iterator(end2), make_reverse_iterator(begin2), make_reverse_iterator(end1), make_reverse_iterator(begin1), right_bound);
		VectorWithNegativeIndices right(pre_right);

		for (int i = -size1; i <= size2; ++i)
			right[i - size2 + size1] = getDiagonalLength(size1, size2, i - size2 + size1) - pre_right[i];

		for (int diagonal = -left_bound; diagonal <= left_bound; diagonal += 2)
		if (-size2 <= diagonal && diagonal <= size1 && -right_bound <= diagonal + size2 - size1 && diagonal + size2 - size1 <= right_bound)
		if (right[diagonal] <= left[diagonal]){
			setPositionOnDiagonal(diagonal, left[diagonal], size1, size2, position1, position2);
			return;
		}

	}

	void buildLongestCommonSubsequence(iterator begin1, iterator end1, iterator begin2, iterator end2, int distance, std::vector<int> &recipe){
		int size1 = std::distance(begin1, end1), size2 = std::distance(begin2, end2);

		if (begin1 == end1){
			while (begin2 != end2){
				pushToRecipe(recipe, +1);
				++begin2;
			}
			return;
		}

		if (begin2 == end2){
			while (begin1 != end1){
				pushToRecipe(recipe, -1);
				++begin1;
			}
			return;
		}


		if (distance == 0){ // special case = distance is 0
			while (begin1 != end1){
				pushToRecipe(recipe);
				++begin1;
			}

			return;
		}

		if (distance == 1){ //special case = distance is 1
			assert(abs(size1 - size2) == 1);
			if (size1 < size2){
				while (*begin1 == *begin2){
					pushToRecipe(recipe);
					++begin1;
					++begin2;
				}
				pushToRecipe(recipe, +1);
				while (begin1 != end1){
					pushToRecipe(recipe);
					++begin1;
				}
			}
			else{
				while (*begin1 == *begin2){
					pushToRecipe(recipe);
					++begin1;
					++begin2;
				}
				pushToRecipe(recipe, -1);
				++begin1;
				while (begin2 != end2){
					pushToRecipe(recipe);
					++begin2;
				}

			}

			return;
		}

		int position1, position2;
		int left_bound = (distance + 1) / 2;
		int right_bound = distance - left_bound;

		setDivisionPoint(begin1, end1, begin2, end2, distance, position1, position2);

		buildLongestCommonSubsequence(begin1, begin1 + position1, begin2, begin2 + position2, left_bound, recipe);
		buildLongestCommonSubsequence(begin1 + position1, end1, begin2 + position2, end2, right_bound, recipe);
		
	}

	void setDiffTorecipe(const std::vector<int> &sequence1, const std::vector<int> &sequence2, std::vector<int> &recipe){
		int distance = getDistance(sequence1.begin(), sequence1.end(), sequence2.begin(), sequence2.end());
		buildLongestCommonSubsequence(sequence1.begin() , sequence1.end(), sequence2.begin(), sequence2.end(), distance, recipe);
	}


	std::vector<int> diff(const std::vector<std::string> &text1, const std::vector<std::string> &text2){
		std::vector<int> v1(text1.size()), v2(text2.size());
		std::vector<int> recipe;
		std::vector<std::string> all_words;

		for (auto &str : text1)
			all_words.push_back(str);
		for (auto &str : text2)
			all_words.push_back(str);

		std::sort(all_words.begin(), all_words.end());

		for (int i = 0; i < (int) text1.size(); ++i){
			v1[i] = std::lower_bound(all_words.begin(),all_words.end(),text1[i])-all_words.begin();
		}

		for (int i = 0; i < (int) text2.size(); ++i){
			v2[i] = std::lower_bound(all_words.begin(), all_words.end(), text2[i]) - all_words.begin();
		}

		setDiffTorecipe(v1, v2, recipe);

		return recipe;
	}


};